This invention relates to the design of microelectronic circuits and systems, and more particularly, to simulators for evaluating the performance of microelectronic circuits and systems prior to fabrication.
In the process of designing circuits, particularly large scale integrated circuits, it is normal practice to mathematically model the electrical circuits. Many circuit simulators have been developed to mathematically model the circuits. Particularly, the outputs of the circuit are modeled as a function of the inputs to the circuit. The mathematical model is used to determine various response characteristics of the circuit.
Circuit simulation has long been an essential step in the design and manufacture of microelectronic circuits and systems. Circuit simulators are typically software based and are designed to accept a description of the circuit that defines the circuit topology and element values. Simulators typically simulate circuits which contain linear devices such as resistors capacitors and inductors, voltage and current sources and nonlinear devices such as diodes, bipolar junction transistors (BJT), junction field effect transistors (JFET) and metal oxide semiconductor field effect transistors (MOSFET). The simulator can typically be configured to perform DC analysis, AC small signal analysis and transient analysis.
The modeling of the larger overall circuit can be extremely complex in large scale integrated (LSI) circuits, very large scale integrated (VLSI) circuits, and ultra large scale integrated (ULSI) circuits. Simulation of extremely LSI, VLSI, and ULSI circuits require better simulators. As the size and complexity of circuits has grown, so has the need for simulators that are capable of testing larger and more complex circuits.
A traditional simulation tool, such as a dynamic simulator (SPICE, for example), can be used. However, because of the large number of circuit elements involved, a complete simulation becomes extremely time consuming and may exceed the storage capability of the processing system on which the simulation is run. Dynamic simulators such as SPICE-like simulators that are based on integration of nonlinear ordinary differential equations are useful in analyzing nonlinear circuit but are relatively inefficient for highly interconnected circuits or networks.
In recent years, moment matching techniques, e.g., [1]-[3], havegrown to be among the most popular linear circuit simulation techniques. The moments of a transfer function of order n results from expanding the transfer function into a Taylor series around s=0 as given by                                           H            ⁡                          (              s              )                                =                                                    1                +                                                      a                    1                                    ⁢                  s                                +                                                      a                    2                                    ⁢                                      s                    2                                                  +                …                +                                                      a                    m                                    ⁢                                      s                    m                                                                              1                +                                                      b                    1                                    ⁢                  s                                +                                                      b                    2                                    ⁢                                      s                    2                                                  +                …                +                                                      b                    n                                    ⁢                                      s                    n                                                                        =                          1              +                                                m                  1                                ⁢                s                            +                                                m                  2                                ⁢                                  s                  2                                            +                                                m                  3                                ⁢                                  s                  3                                            +              …                                      ⁢                  xe2x80x83                ,                            (        1        )            
The ith moment of the transfer function m1 is the coefficient of s1 in the series expansion. To illustrate the relation between the moments, poles, and residues of the transfer function, (1) can be expressed as a partial fractions sum given by                                           H            ⁡                          (              s              )                                =                                                    k                1                                            s                -                                  p                  1                                                      +                                          k                2                                            s                -                                  p                  2                                                      +            …            +                                          k                n                                            s                -                                  p                  n                                                                    ,                            (        2        )            
where p1 is the ith pole of the transfer function and k1 is the corresponding residue. By expanding each term in equation (2) into powers of s, the moments of H(s) can be expressed as                                                                                           m                  0                                =                                  -                                      (                                                                                            k                          1                                                                          p                          1                                                                    +                                                                        k                          2                                                                          p                          2                                                                    +                      …                      +                                                                        k                          n                                                                          p                          n                                                                                      )                                                              ,                                                                                                            m                  1                                =                                  -                                      (                                                                                            k                          1                                                                          p                          1                          2                                                                    +                                                                        k                          2                                                                          p                          2                          2                                                                    +                      …                      +                                                                        k                          n                                                                          p                          n                          2                                                                                      )                                                              ,                                                            ⋮                                                                              m                                                      2                    ⁢                    n                                    -                  1                                            =                              -                                                      (                                                                                            k                          1                                                                          p                          1                                                      2                            ⁢                            n                                                                                              +                                                                        k                          2                                                                          p                          2                                                      2                            ⁢                            n                                                                                              +                      …                      +                                                                        k                          n                                                                          p                          n                                                      2                            ⁢                            n                                                                                                                )                                    .                                                                                        (        3        )            
This favorable reciprocal relation between the moments and the poles stresses the dominant poles with smaller magnitudes. Dominant poles are of most interest when evaluating the transient response. This characteristic makes the moments very popular in circuit simulation. Moreover, the moments around s=0 can be calculated very easily for tree structured and tree like interconnect in linear time with the number of elements in the circuit [1]-[5]. Path tracking techniques for efficiently calculating the moments for tree and tree like structures where introduced in [4] and [5]. Note that tree like structures include capacitively and inductively coupled trees. Also, other techniques have been developed in [5] to extend the efficiency of path tracking techniques to circuits with few resistive and inductive loops. The overwhelming majority of interconnects in integrated circuits fall into these categories of circuits. The efficiency of calculating the moments around s=0 further increased the popularity of moment matching techniques.
Numerous moment matching techniques are known in the art for large linear circuit analysis. One technique in particular is the asymptotic Waveform Evaluation (AWE) algorithm. The AWE technique [2], [3] employs moment matching by calculating the first 2q moments of the transfer function around s=0 to determine the first q dominant poles and corresponding residues of the transfer function. The moments at node j are approximated by                                                                                           m                  0                  j                                =                                  -                                      (                                                                                            k                          1                          j                                                                          p                          1                                                                    +                                                                        k                          2                          j                                                                          p                          2                                                                    +                      …                      +                                                                        k                          4                          j                                                                          p                          q                                                                                      )                                                              ,                                                                                                            m                  1                  j                                =                                  -                                      (                                                                                            k                          1                          j                                                                          p                          1                          2                                                                    +                                                                        k                          2                          j                                                                          p                          2                          2                                                                    +                      …                      +                                                                        k                          q                          j                                                                          p                          q                          2                                                                                      )                                                              ,                                                            ⋮                                                                              m                                                      2                    ⁢                    q                                    -                  1                                j                            =                              -                                                      (                                                                                            k                          1                          j                                                                          p                          1                                                      2                            ⁢                            q                                                                                              +                                                                        k                          2                          j                                                                          p                          2                                                      2                            ⁢                            q                                                                                              +                      …                      +                                                                        k                          q                          j                                                                          p                          q                                                      2                            ⁢                            q                                                                                                                )                                    .                                                                                        (        4        )            
where the terms representing poles with magnitude larger than pq are neglected and p1 less than p2 less than  . . .  less than pq. Hence, the first q most dominant poles and corresponding residues can be calculated by solving the set of 2q nonlinear equations with 2q variables in equation (4). Indirect methods to solve equation (4) were also developed in [2].
The process by which the moments are determined does not allow calculating the moments at few selected nodes of a circuit and the moments have to be calculated at all nodes since the i+1 moment at any node j depends on the ith moments at all the nodes [1]-[5]. However, the AWE techniques only uses the moments at a single node at a time to calculate the response at that node and all the moments calculated at other nodes are not used. Hence, techniques of the prior art such as the AWE techniques are referred to as Single-point Moment Matching (SMM) techniques. These techniques improve the approximation accuracy by calculating more moments at each node.
As will be shown, accuracy can be also improved by using the information in the moments at different nodes simultaneously. However, multiple input circuits are becoming increasingly cammon in integrated circuits with the increasing importance a analyzing interconnects with capacitive and inductive coupling. Also, important structures such as the power distribution networks are typically multi-input circuits. A major problem with SMM techniques is the inherent numerical instability with higher order approximations. The set of equations (4) is very sensitive to numerical errors with high q due to the high powers of the poles involved. Even with a moderate disparity in the pole values, higher moments very quickly contain no information about larger magnitude poles due to truncation errors. For that reason SMM techniques are limited to less than eight to ten poles [4]-[6]. With complicated integrated circuits, increasing inductance effects, higher inductive and capacitive coupling, and higher operating frequencies, approximations with orders higher than can be achieved by single-point moment matching become necessary. The poles of a circuit effectively represent its harmonics. The more complex the harmonics, the greater the number of poles required for accurate simulation. For simple RC (resistive-capacitance) circuits, usually only a few dominant poles are required for high accuracy simulation. Under such conditions, the AWE approximation method is quite accurate and is widely used for simple RC circuits. But, for today""s more complex RLC circuits (resistive-inductive-capacitance) multi-input circuits, the harmonics becomes complex and the number of poles required for accurately simulating the circuit becomes quite large. As a general rule, AWE breaks down when poles exceed eight in number.
To overcome this limitation of AWE, techniques such as Complex Frequency Hopping (CFH) have been proposed to determine higher number of poles [7]-[8]. When circuit harmonics is complex, an approximation method is needed that is more accurate than AWE. xe2x80x9cComplex Frequency Hoppingxe2x80x9d (CFH) represents a more accurate method.
Mathematically speaking, Complex Frequency Hopping works by calculating poles around s=0, but then xe2x80x9chopsxe2x80x9d to calculate poles around xe2x80x9csxe2x80x9d at some harmonic frequency greater than 0. The common poles calculated at both xe2x80x9chopsxe2x80x9d (s=0 and s=non-zero) are said to be xe2x80x9caccurate,xe2x80x9d and the ones found only by one of the two hops are said to be xe2x80x9cinaccurate.xe2x80x9d
The Complex Frequency Hopping method is more accurate than AWE, but it is also time consuming and therefore slow to implement. For certain applications, such as microwave circuit design, high speed is not required (presumably because there are less design iterations or the circuits have a fairly modest number of nodes), so the method can work quite nicely. Because the CFH technique calculates the moments around several frequency points instead of only around s=0, a different set of poles is emphasized around the selected frequency point in each set of moments, allowing the calculation of high number of poles. However, calculating the moments around sxe2x89xa00 cannot use path tracking techniques and is much more complicated than calculating the moments around s=0, especially when inductive and capacitive coupling are present. Also, determining the set of points around which the moments are calculated is a non-trivial task.
Another set of techniques becoming increasingly if popular are based on Krylov sub-spaces and Lanczos process, e.g., [9]-[14]. These techniques implicitly match the moments of the circuit by using a different set of vectors that have the same span of the moment vectors but are much more numerically stable. High approximation orders can be achieved by using these techniques. The clear and unambiguous inference inherent to the prior art is, therefore, that explicit moment matching around s=0 cannot be used to calculate high order approximations. While Krylov space methods are quite old, some new methods based upon Krylov space methods have been developed in the 1990""s. These methods are more accurate than AWE, but are slow and are less accurate than CFH.
The foregoing background information, together with other aspects of the prior art, including those teachings useful in light of the present invention, are disclosed more fully and better understood in light of the following references, each of which is incorporated herein in its entirety.
[1] L. T. Pillage and R. A. Rohrer, xe2x80x9cDelay Evaluation with Lumped Linear RLC Interconnect Circuit Models,xe2x80x9d Proceedings of the Caltech Conference on VLSI, pp. 143-158, May 1989.
[2] L. T. Pillage and R. A. Rohrer, xe2x80x9cAsymptotic Waveform Evaluation for Timing Analysis,xe2x80x9d IEEE Transactions on Computer-Aided Design, Vol. CAD-9, No. 4, pp. 352-366, April 1990.
[3] T. K. Tang and M. S. Nakhla, xe2x80x9cAnalysis of High-Speed VLSI Interconnects Using the Asymptotic Waveform Evaluation Techniques,xe2x80x9d IEEE Transactions on Computer-Aided Design, Vol. CAD-11, No. 3, pp. 341-352, March 1992.
[4] C. L. Ratzlaff, I Fast Algorithm for Computing the Time Moments of RLC Circuits, Masters thesis, University of Texas at Austin, Austin, Tex., May 1991.
[5] C. L. Ratzlaff, N. Gopal, and L. T. Pillage, xe2x80x9cRICE: Rapid Interconnect Circuit Evaluator,xe2x80x9d Proceedings of the IEEE/ACM Design Automation Conference, pp. 555-560, June 1991.
[6] D. F. Anastasakis, N. Gopal, S. Y. Kim, and L. T. Pillage, xe2x80x9cOn the Stability of Approximations in Asymptotic Waveform Evaluation,xe2x80x9d Proceedings of the IEEE/ACM Design Automation Conference, pp. 207-212, June 1992.
[7] R. Achar, M. S. Nakhla and Q. Zhang xe2x80x9cFull-Wave Analysis of High-Speed VLSI Interconnects Using Complex Frequency Hopping,xe2x80x9d IEEE Transactions on Computer-Aided Design, Vol. CAD-17, No. 10, pp. 997-1016, October 1998.
[8] E. Chiprout and M. S. Nakhla, xe2x80x9cAnalysis of Interconnect Networks Using Complex Frequency Hopping,xe2x80x9d IEEE Transactions on Computer-Aided Design, Vol. CAD-14, pp. 186-200, February 1995.
[9] P. Feldmann and R. W. Freund, xe2x80x9cEfficient Linear Circuit Analysis by Pade Approximation via the Lancozos Process,xe2x80x9d IEEE Transactions on Computer-Aided Design, Vol. CAD-14, No. 5, pp. 639-649, May 1995.
[10] P. Feldmann and R. W. Freund, xe2x80x9cReduced-Order Modeling of Large Linear Subcircuits via Block Lanczos Algorithm,xe2x80x9d Proceedings of the IEE/ACM Design Automation Conference, pp. 474-479, June 1995.
[11] M. Silveira, M. Kamon, and J. White, xe2x80x9cEfficient Reduced-Order Modeling of Frequency-Dependent Coupling Inductances Associated with 3-D Interconnect Structures,xe2x80x9d Proceedings of the IEEE/ACM Design Automation Conference, pp. 376-380, June 1995.
[12] D. L. Boley, xe2x80x9cKrylov Space Methods on State-Space Control Models,xe2x80x9d Journal of Circuits, Systems, and Signal Processing, Vol. 13, No. 6, pp. 733-758, May 1994.
[13] A. Odabasioglu, M. Celik, and L. T. Pillage, xe2x80x9cPRIMA: Passive Reduced-Order Interconnect Macromodeling Algorithm,xe2x80x9d IEEE Transactions on Computer-Aided Design, Vol. CAD-17, No. 8, pp. 645-654, August 1998.
[14] P. Feldmann and R. W. Freund, xe2x80x9cReduced-Order Modeling of Large Passive Linear Circuits by Means of the SyPVL Algorithm,xe2x80x9d Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, pp. 280-287, November 1996.
Objects of the Invention.
Accordingly, the prior art has associated with it numerous shortcomings and deficiencies, including those outlined above. AWE process time is directly proportional to xe2x80x9cq,xe2x80x9d where xe2x80x9cqxe2x80x9d represents the number of reduced order poles. Process time associated with xe2x80x9cKrylov Space Methodsxe2x80x9d is directly proportional to xe2x80x9cq2, but the xe2x80x9corderxe2x80x9d of the circuit (xe2x80x9cnxe2x80x9d=number of nodes) is also a factor in determining process time. As expressed above, AWE is commonly used for simple RC circuits. CFH is time consuming, but often applied where high-speed simulation isn""t required, such as with microwave circuits. Today""s large RLC circuits have very complex harmonics, and multiple circuit inputs. What is needed is a method that is both fast and accurate for today""s more complex VLSI (very large scale integrated) circuits. It is, therefore, an object of the present invention to provide a method and/or apparatus for generating and analyzing a reduced-order model of a linear circuit, such method and apparatus as can simultaneously match the moments at several nodes of a circuit using explicit moment matching around s=0.
It will be understood by those skilled in the art that one or more aspects of this invention can meet certain objectives while one or more other aspects can meet certain other objectives. Each objective may not apply equally, in all its respects, to every aspect of this invention. As such, the following objects can be viewed in the alternative with respect to any one aspect of this invention.
It is an object of the present invention to provide an efficient method and apparatus for simulating linear and nonlinear circuits and systems using model order reduction.
Another object of the present invention is to provide an efficient method and apparatus for simulating linear and nonlinear circuits and systems using model order reduction using a moment matching technique which requires a significantly fewer number of moments than are required using known moment techniques for calculating a reduced order model.
Yet another object of the present invention to provide a moment matching technique the computational efficiency of which increases with the number of inputs to a circuit or system being simulated.
A further object of the present invention to provide a moment matching technique which is suitable for parallel processing.
It is a feature of the present invention that the moment matching technique requires only q+I moments, where q is the approximation order and I is the number of inputs of the circuit or system being simulated.
Another feature of the invention is to provide a model order reduction technique capable of achieving high order approximations that are not achievable using single-point explicit moment matching at even better computational efficiency.
Other objects, features, benefits and advantages of the present invention will be apparent from the following summary and descriptions of various preferred embodiments, and will be readily apparent to those skilled in the art having knowledge of various model order reduction and/or single moment matching techniques. Such objects, features, benefits and advantages will be apparent from the above as taken in conjunction with the accompanying examples, data, mathematical relationships, figures and all reasonable inferences to be drawn therefrom, alone or with consideration of the references incorporated herein.
The present invention provides methods and related apparatus, together with techniques, for simulating linear and nonlinear circuits by model order reduction using a multi-point moment matching (MMM) technique provided by the present invention. By exploiting the spatial information in the moments, the use of MMM significantly reduces the number of moments required to achieve a specific accuracy and thus, improves computational efficiency. As explained more fully below, the reduction in the number of moments by using MMM, rather than the SMM techniques of the prior art, increases with the number of inputs to the subject circuit.
Multi-point Moment Matching (MMM) techniques, methods and related apparatus simultaneously match moments at several nodes of a circuit using explicit moment matching around s=0. AWE has been referred to above as a Single-Moment Matching (SMM) method of circuit approximation because it looks at each node in isolation of other nodes an approach that creates inefficiencies in terms of processing time and numerical accuracy. The present invention provides a Multiple-Moment Matching (MMM) algorithm that does consider the inter-dependencies among multiple nodes, but does so in a manner that is highly efficient. As compared to the well-known Single-point Moment Matching (SMM) techniques (such as AWE), MMM has several advantages. First, the number of moments required by MMM is significantly lower than SMM for a reduced order model of the same accuracy, which directly translates into computational efficiency. This higher computational efficiency of MMM as compared to SMM increases with the number of inputs to the circuit. Second, MMM has much better numerical stability as compared to SMM. This characteristic of MMM allows the calculation of an arbitrarily high order approximation of a linear system, achieving the required accuracy for systems with complex responses. Finally, MMM is highly suitable for parallel processing techniques especially for higher order approximations while using SMM requires calculating the moments sequentially and SMM cannot be adapted to parallel processing techniques. The invention also lends itself to parallel processing, a feature that is very important when simulating today""s multi-input circuits that have inherent interdependencies among the multiple inputs. As the number of inputs grows, the processing speed of the invention grows exponentially in contrast to that of the AWE and other Single-point Moment Matching methods. AWE, while fast, does not allow for parallel processing, which is important as the number of circuit inputs increase. Components of today""s system circuits are effectively less isolated from one another, so that multiple inputs must be treated at once. By enabling parallel processing, the invention (MMM) not only is from 2-10 times faster than AWE, but also is much more accurate and numerically stable. MMM is simpler than CFH, and unlike CFH it allows for so-called xe2x80x9cpath tracing. This results from the fact that the present invention calculates poles around s=0, and that CFH calculates poles around multiple points.xe2x80x9d MMM is an explicit moment matching method. Prior to this invention, it was commonly believed that explicit moment matching methods around s=0 (calculating around s=0 simplifies things greatly) could not be used to calculate high-order approximations (high-order implying very large scale circuits). MMM takes advantage of certain xe2x80x9cspatialxe2x80x9d relationships to simplify circuit approximation while at the same time looking at interdependencies among nodes. The simplification reduces processing time, and treating nodes interdependently increases accuracy. Specifically, MMM enables the number of moments to be reduced, while at the same time it does so simply by viewing poles around s=0. Achieving both high accuracy and speed becomes important for circuits with complex responses. These can include circuit xe2x80x9cinterconnectsxe2x80x9d with capacitive and inductive coupling, power distribution networks and the like.
Determining a reduced order system of order q using the MMM technique requires only q+I moments, where q is the approximation and I is the number of inputs to the circuit. The MMM technique can be used with single input circuits or networks and/or multiple input circuits or networks. The MMM technique requires fewer moments because it exploits the fact that there is a common set of poles at all the nodes of a circuit or network. Because the q poles are common to all the nodes, adding an extra node only adds q new variables for q residues at the extra node. Therefore, the number of variables, when simultaneously considering q nodes, is q poles and q2 residues, and the MMM technique needs only to match q(q+I) moments which are q+I moments at q nodes. Using only q+I moments instead of q(I+1) moments does not reduce the accuracy of an approximation based upon the MMM technique as compared to single point moment matching.
The numerical stability of a q order approximation calculated using the MMM technique increases as the number of inputs to the circuit increases. Therefore, in accordance with another aspect of the invention, in calculating some approximations, dummy inputs are introduced. The introduction of dummy inputs reduces truncation errors in high order approximations due to the high powers of the poles involved. Dummy inputs can be added until the maximum power of the poles in the approximation is sufficiently low to guarantee the numerical stability of the approximation.
Higher computational efficiency as compared to known techniques, allowing the MMM technique to calculate an arbitrarily high order approximation of a linear system, achieving the required accuracy for systems with complex responses. Moreover, the MMM technique is suitable for parallel processing techniques, especially for high order approximations.
In accordance with another aspect of the invention, there is provided an interconnect evaluator which uses the MMM technique to simulate very large scale integration (VLSI) interconnects. The MMM simulations can produce desired outputs, including circuit speed, power consumption, signal coupling noise and signal skew, for example.
Further in accordance with the invention, there is provided a nonlinear circuit simulator including a circuit linearizer, which linearizes the nonlinear circuit about an operating point, and a simulator based on the MMM technique for simulating the linearized circuit and determining a new operating point which is supplied to the circuit linearizer. Thus, the circuit is linearized several times and the resulting linear circuits are simulated. The simulations that are obtained are combined over time to represent the response of the nonlinear circuit.
In accordance with yet another aspect of the invention, there is provided a simulation engine incorporating the MMM technique for providing iterative optimization of a circuit design. The simulation engine evaluates the performance of the circuit in terms of key operating parameters, such as speed, power consumption and signal integrity. If the circuit performance does not meet the design goals, the circuit is modified based upon a circuit optimization algorithm and the performance is evaluated again. The iterative process is repeated until the circuit meets the design goals or reaches optimum performance.